package com.origin.niuke.dfs;

import java.util.Arrays;

/**
 * NC226 被围绕的区域
 * 算法：深度优先搜索
 *
 * @author yezh
 * @date 2022/12/1 22:04
 */
public class NC226 {

    public char[][] surroundedArea(char[][] board) {
        // write code here
        int n = board.length, m = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[0][i] == 'O') dfs(0, i, board);
            if (n != 1 && board[n - 1][i] == 'O') dfs(n - 1, i, board);
        }
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') dfs(i, 0, board);
            if (m != 1 && board[i][m - 1] == 'O') dfs(i, m - 1, board);
        }
        System.out.println(Arrays.deepToString(board));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        return board;
    }

    void dfs(int i, int j, char[][] board) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        // 这里的判断条件时 != 'O', 而不是 == 'X', 后者会死循环, 因为会把 'O' 变成 'A'
        if (board[i][j] != 'O') return;
        if (board[i][j] == 'O') board[i][j] = 'A';
        dfs(i, j - 1, board);
        dfs(i, j + 1, board);
        dfs(i - 1, j, board);
        dfs(i + 1, j, board);
    }

}
